1. Field of the Invention
The present invention relates to a compiler for compiling a program written in a high-level programming language into a machine language program.
2. Description of the Related Art
In recent years, there have been many improvements in the program development due to writing programs in high-level programming languages, such as C language.
By using high-level programming languages, the programmer can express such processes as the storage, operation and transmission of numerical values as operations (steps) which use the variables as their operands. Since these variables can be freely defined by the programmer, and are used only according to necessity, the programmer is free to write the program according to his/her desires and needs. By compiling these programs (known as source programs), they are converted into machine language programs which can be readily understood by the CPU in the computer. Operations in such machine language programs are expressed as machine language instructions which use the registers and memory as operands, so that during compiling it becomes necessary to assign the variables in the source program to the registers and memory. This assigning process is known as the resource assignment process. By optimally executing this resource assignment process, the code size of the machine language program produced can be reduced to a minimum, with the execution time of the generated program also being optimized.
As for the resources themselves, if memory and registers are compared, then it can be seen that the code size and the execution time of the machine language program can be reduced by setting the registers rather than the memory as operands. However, there are only a small number of registers available, then, before resource assignment is performed, it is usual to investigate the live ranges of the variables to see which variables can be assigned to the same register, with resource assignment being performed based on the results of this investigation. A live range is the range for which the stored value of a variable is valid, with FIG. 1A showing an example program and the live ranges of the variables used therein.
In this drawing, it can be seen that the live ranges for variable x4 and the variable t3 interfere (overlap), which means that these variables cannot be assigned to the same register. Variable t1 and variable t3 do not interfere, so that it is possible to assign these variables to the same register.
Next, the live ranges of all of the variables in the program are expressed as groups of intermediate language steps. Intermediate language steps are show in FIG. 1A as s1, s2, s3, s4 . . . etc. FIG. 1B shows the same live ranges expressed as groups of intermediate language steps. In the example shown in FIG. 1B, the live range of the variable t1 consists of only the intermediate language step s2, while the live range of the variable x consists of the intermediate language steps s8, s9, s10 and s11.
Next, for any pair of variables in the program, the intersection set of the groups of intermediate language steps is found. If the intersection set is vacant, then it is judged that the live ranges of the two variables do not interfere with one another. For the example shown in FIG. 1B, since there is no common element in the groups of intermediate language steps for the live ranges for variable x and variable x4, the intersection set is vacant, so that it is judged that the variables do not interfere with one another. However, since for variable x and variable t3 there is the common element s4 in the two groups of intermediate language steps for the live ranges, the intersection set is not vacant, and, as a result, it is Judged that the live ranges of variable x and variable t3 interfere with one another.
By repeating this investigation of intersection sets, it is determined which variables interfere with each other, with the result shown in FIG. 1C. It can be seen in this table that the live ranges of the variables p1, p2 and p3 interfere with that of the variable t1. In the same way, it can be seen that the live ranges of the variables p1, p2 and p3 also interfere with the live range of the variable x4.
By finding the interference between live ranges as described above, the number of variables to be assigned to a same register can be increased.
However, under the related art described above, there has been the problem that this investigation of the interference of live ranges has been very time-consuming. Given that it is quite normal for the total number of variables in a software program developed by a team of several programmers to be around one hundred, then when adding the variables automatically generated by the compiler in generating the intermediate language program, the total number of variables to be subject to the interference investigation can run to several hundred.
The interference investigation for the live ranges of the variables is performed by finding the group areas, with the number of times these group areas are calculated for n variables being nC2=n(n-1)/2 times (C=combinations), so that if the number n in the hundreds, this number of calculations of group areas will be extremely high. For example, if the number of variables n is set at 100, then nC2 will become 4,950, so that the compiler will have to perform 4,950 investigations of group intersection. If the number of variables n is set at 300, then nC2 will become 44,850, so that the compiler will have to perform 44,850 calculations of group intersection.
Furthermore, when there are a lot of variables which are only used once in the program, or which are redefined after being used once, then there will be an extreme amount of interference between live ranges, so that if there are only a limited number of registers, there is the problem that it will not be possible to assign all of the variables whose live ranges interfere to different registers.